import org.junit.Test;
import test.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 *  二叉树的后序遍历
 */
public class postorderTraversal {

    @Test
    public void test() {
        TreeNode treeNode = new TreeNode(1);
        TreeNode right = new TreeNode(12);
        TreeNode left21 = new TreeNode(211);
        TreeNode right22 = new TreeNode(222);
        right.setLeft(left21);
        right.setRight(right22);
        treeNode.setRight(right);
        TreeNode left1 = new TreeNode(11);
        TreeNode left11 = new TreeNode(111);
        TreeNode right12 = new TreeNode(122);
        left1.setLeft(left11);
        left1.setRight(right12);
        treeNode.setLeft(left1);
        System.out.println(preorderTraversaltest(treeNode));
    }

    public List<Integer> preorderTraversaltest(TreeNode root){
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prevAccess = null;
        while (!stack.isEmpty() || root !=null){
            while (root != null){
                res.add(root.getVal());
                stack.push(root);
                root = root.getLeft();
            }
            root = stack.pop();
            root = root.getRight();
        }

        root = stack.pop();
        if(root.getRight()==null || root.getRight() == prevAccess){
            res.add(root.getVal());
            root = null;
        }else {
            stack.push(root);
            root = root.getRight();
        }

        return res;
    }

}
